# 新进来的数字都会在指定位置顺序中插入

# 初始的时候手里只有一张牌（有序区）
# 每次摸牌的时候都将对应的牌插入到指定的顺序位置（无序区）


def insert_sort(li: list) -> int:
    """
    插入排序, O(n2)
    :param li:
    :return:
    """
    for i in range(1, len(li)):
        tmp = li[i]
        # 有序区的下标范围是[0, i-1]
        j = i - 1
        while j >= 0 and li[j] > tmp:
            # 不断的将 j 往前挪，直到 li[j] <= tmp
            li[j+1] = li[j]
            j -= 1

        # 将tmp插入到有序区
        li[j+1] = tmp
    return li